package org.example;

import java.util.Scanner;

public class zhuxinsuan {

    public static String smallestPalindromeExtension(String s) {
        int n = s.length();
        // dp[i][j] 表示将 s[i:j+1] 变为回文所需的最小添加字符串长度
        int[][] dp = new int[n][n];
        // parent[i][j] 用于回溯最小添加字符串的内容
        int[][] parent = new int[n][n];

        // 初始化 dp 数组和对角线（单个字符是回文，不需要添加）
        for (int i = 0; i < n; i++) {
            dp[i][i] = 0;
        }

        // 填充 dp 数组
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1]; // 不需要添加字符
                    parent[i][j] = -1; // 标记为不需要回溯
                } else {
                    dp[i][j] = dp[i + 1][j] + 1; // 添加 s[i] 的复制
                    parent[i][j] = 0; // 标记为回溯到 dp[i+1][j] 并添加 s[i]
                    if (dp[i][j] > dp[i][j - 1] + 1) { // 检查另一种添加方式
                        dp[i][j] = dp[i][j - 1] + 1; // 添加 s[j] 的复制
                        parent[i][j] = 1; // 标记为回溯到 dp[i][j-1] 并添加 s[j]
                    }
                }
            }
        }

        // 回溯最小添加字符串的内容
        StringBuilder toAdd = new StringBuilder();
        int i = 0, j = s.length() - 1;
        while (i <= j) {
            if (parent[i][j] == -1) {
                i++;
                j--;
            } else if (parent[i][j] == 0) {
                toAdd.insert(0, s.charAt(i)); // 在开头添加 s[i]
                i++;
            } else {
                toAdd.append(s.charAt(j)); // 在末尾添加 s[j]
                j--;
            }
        }

        // 返回扩展后的回文字符串
        return s + toAdd.toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入任意字符串：");
        String input = scanner.nextLine();
        scanner.close();

        String result = smallestPalindromeExtension(input);
        System.out.println("原始字符串： " + input);
        System.out.println("扩展为回文字符串： " + result);
    }
}